Rujukan Portugis pertama mengenai Melaka muncul selepas Vasco da Gama kembali dari ekspedisinya ke Calicut yang membuka laluan langsung ke India menerusi Tanjung Harapan. Ia digambarkan sebagai sebuah bandar yang terletak 40 hari pelayaran dari India, di mana cengkih, pala, porselin dan sutera dijual, dan kononnya diperintah oleh seorang raja yang dapat mengumpulkan 10,000 orang untuk berperang dan merupakan seorang Kristen.[10] Sejak itu, Raja Manuel telah menunjukkan minat untuk membuat hubungan dengan Melaka, mempercayainya sebagai berada di, atau sekurang-kurangnya dekat, antimeridian Tordesillas.[11] Pada tahun 1505, Dom Francisco de Almeida telah dihantar oleh Raja Manuel I dari Portugis sebagai Viceroy Portugis India pertama, yang ditugaskan untuk, antara lain, mengetahui lokasi yang tepat.

Bagaimanapun, De Almeida tidak dapat menumpukan sumber untuk usaha tersebut, dan hanya menghantar dua utusan Portugis yang menyamar pada bulan Ogos 1506, Francisco Pereira dan Estevão de Vilhena, menumpang sebuah kapal saudagar Muslim. Misi itu dibatalkan apabila mereka dikesan dan hampir terbunuh di Pantai Coromandel, nyaris gagal untuk kembali ke Cochin menjelang November.[12]